﻿#define _CRT_SECURE_NO_WARNINGS 1
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<math.h>
#include<time.h>
#include<assert.h>
#include<stddef.h>
#include<stdbool.h>

struct ListNode{int val;struct ListNode* next;};
struct ListNode* SList()
{
	struct ListNode* n1 = (struct ListNode*)malloc(sizeof(struct ListNode)); assert(n1);
	struct ListNode* n2 = (struct ListNode*)malloc(sizeof(struct ListNode)); assert(n2);
	struct ListNode* n3 = (struct ListNode*)malloc(sizeof(struct ListNode)); assert(n3);
	struct ListNode* n4 = (struct ListNode*)malloc(sizeof(struct ListNode)); assert(n4);
	struct ListNode* n5 = (struct ListNode*)malloc(sizeof(struct ListNode)); assert(n5);
	struct ListNode* n6 = (struct ListNode*)malloc(sizeof(struct ListNode)); assert(n6);
	struct ListNode* n7 = (struct ListNode*)malloc(sizeof(struct ListNode)); assert(n7);

	n1->val = 9;
	n2->val = 7;
	n3->val = 4;
	n4->val = 5;
	n5->val = 6;
	n6->val = 1;
	n7->val = 4;

	n1->next = n2;
	n2->next = n3;
	n3->next = n4;
	n4->next = n5;
	n5->next = n6;
	n6->next = n7;
	n7->next = NULL;

	return n1;
}
void ListPrint(struct ListNode* list)
{
	assert(list);
	while (list != NULL)
	{
		printf("%d->", list->val);
		list = list->next;
	}
	printf("NULL\n");
}




//MyCircularQueue(k) : 构造器，设置队列长度为 k 。
//Front : 从队首获取元素。如果队列为空，返回 - 1 。
//Rear : 获取队尾元素。如果队列为空，返回 - 1 。
//enQueue(value) : 向循环队列插入一个元素。如果成功插入则返回真。
//deQueue() : 从循环队列中删除一个元素。如果成功删除则返回真。
//isEmpty() : 检查循环队列是否为空。
//isFull() : 检查循环队列是否已满。
typedef int CQDataType;
typedef struct 
{
	CQDataType* arr;
	int Front;
	int Rear;
	int capacity;
} MyCircularQueue;

// 初始化
MyCircularQueue* myCircularQueueCreate(int k) 
{
	MyCircularQueue* obj = (MyCircularQueue*)malloc(sizeof(MyCircularQueue));
	obj->capacity = k + 1;
	obj->arr = (CQDataType*)malloc(sizeof(CQDataType) * obj->capacity);
	obj->Front = 0;
	obj->Rear = 0;
	return obj;
}
// 向循环队列插入一个元素
bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) 
{
	if ((obj->Rear + 1) % obj->capacity == obj->Front)
		return false;

	obj->Rear = obj->Rear % obj->capacity;
	obj->arr[obj->Rear++] = value;
	return true;
}
// 从循环队列中删除一个元素
bool myCircularQueueDeQueue(MyCircularQueue* obj) 
{
	if (obj->Front == obj->Rear)
		return false;

	obj->Front = (++obj->Front) % obj->capacity;
	return true;
}
// 从队首获取元素
int myCircularQueueFront(MyCircularQueue* obj) 
{
	if (obj->Front == obj->Rear)
		return -1;

	return obj->arr[obj->Front];
}
// 获取队尾元素
int myCircularQueueRear(MyCircularQueue* obj) 
{
	if (obj->Front == obj->Rear)
		return -1;

	return obj->arr[obj->Rear - 1];
}
// 检查循环队列是否为空
bool myCircularQueueIsEmpty(MyCircularQueue* obj) 
{
	return (obj->Front == obj->Rear);
}
// 检查循环队列是否已满
bool myCircularQueueIsFull(MyCircularQueue* obj) 
{
	return ((obj->Rear + 1) % obj->capacity == obj->Front);
}
// 释放
void myCircularQueueFree(MyCircularQueue* obj) 
{
	free(obj->arr);
	obj->capacity = obj->Front = obj->Rear = 0;
	free(obj);
}








/*
// 给定单个链表的头 head ，使用 插入排序 对链表进行排序，并返回 排序后链表的头 。
struct ListNode* FindPushPrevNode(struct ListNode* sortHead, int val)
{
	struct ListNode* cur = sortHead;
	while ((cur->next != NULL) && (cur->next->val < val))
		cur = cur->next;

	return cur;
}
struct ListNode* insertionSortList(struct ListNode* head) 
{
	if (head == NULL)
		return NULL;

	struct ListNode* sortHead = (struct ListNode*)malloc(sizeof(struct ListNode));
	if (sortHead == NULL)
	{
		perror("insertionSortList.malloc");
		return NULL;
	}
	struct ListNode* sortTail = head;
	sortHead->next = sortTail;

	struct ListNode* cur = head->next;
	struct ListNode* curPrev = head;
	while (cur != NULL)
	{
		if (cur->val < sortTail->val)
		{
			struct ListNode* curNext = cur->next;
			struct ListNode* PushPrevNode = FindPushPrevNode(sortHead, cur->val);
			struct ListNode* PushNextNode = PushPrevNode->next;

			PushPrevNode->next = cur;
			cur->next = PushNextNode;
			sortTail->next = curNext;

			cur = curNext;
			curPrev = sortTail;
		}
		else
		{
			curPrev = curPrev->next;
			sortTail = sortTail->next;
			cur = cur->next;
		}
	}

	sortTail->next = NULL;
	
	struct ListNode* result = sortHead->next;
	free(sortHead); 
	sortHead = NULL; 
	return result;
}
int main()
{
	struct ListNode* list = SList();
	struct ListNode* retlist = insertionSortList(list);
	ListPrint(retlist);

	return 0;
}
*/





/*
// 在一个排序的链表中，存在重复的结点，请删除该链表中重复的结点，重复的结点不保留，返回链表头指针。 
// 例如，链表 1->2->3->3->4->4->5  处理后为 1->2->5
struct ListNode* deleteDuplication(struct ListNode* pHead)
{
	if (pHead == NULL)
		return NULL;

	struct ListNode* deleteHead = NULL;
	struct ListNode* deleteTail = NULL;

	struct ListNode* cur = pHead;
	while (cur != NULL)
	{
		if ((cur->next != NULL) && (cur->val == cur->next->val))
		{
			int some = cur->val;
			while ((cur != NULL) && (cur->val == some))
				cur = cur->next;
		}
		else
		{
			if (deleteHead == NULL)
			{
				deleteHead = deleteTail = cur;
			}
			else
			{
				deleteTail->next = cur;
				deleteTail = deleteTail->next;
			}

			cur = cur->next;
		}

	}

	if(deleteTail != NULL)
		deleteTail->next = NULL;
	return deleteHead;
}
int main()
{
	struct ListNode* list = SList();
	struct ListNode* retlist = deleteDuplication(list);
	ListPrint(retlist);

	return 0;
}
*/






/*
struct Node
{ 
	int val; 
	struct Node* next;
	struct Node* random;
};
struct Node* RandomList()
{
	struct Node* n1 = (struct Node*)malloc(sizeof(struct Node)); assert(n1);
	struct Node* n2 = (struct Node*)malloc(sizeof(struct Node)); assert(n2);
	struct Node* n3 = (struct Node*)malloc(sizeof(struct Node)); assert(n3);
	struct Node* n4 = (struct Node*)malloc(sizeof(struct Node)); assert(n4);
	struct Node* n5 = (struct Node*)malloc(sizeof(struct Node)); assert(n5);

	n1->val = 7;
	n2->val = 13;
	n3->val = 11;
	n4->val = 10;
	n5->val = 1;

	n1->next = n2;
	n2->next = n3;
	n3->next = n4;
	n4->next = n5;
	n5->next = NULL;

	n1->random = NULL;
	n2->random = n1;
	n3->random = n5;
	n4->random = n3;
	n5->random = n1;

	return n1;
}
void RandomListPrint(struct Node* list)
{
	assert(list);
	struct Node* cur = list;
	while (cur != NULL)
	{
		printf("%d->", cur->val);
		cur = cur->next;
	}
	printf("NULL\n");

	cur = list;
	int count = 1;
	while (cur != NULL)
	{
		if (cur->random == NULL)
			printf("n%d->random = NULL\n", count++);
		else
			printf("n%d->random->val = %d\n", count++, cur->random->val);

		cur = cur->next;
	}
}

// 给你一个长度为 n 的链表，每个节点包含一个额外增加的随机指针 random ，该指针可以指向链表中的任何节点或空节点。
struct Node* BuyRandomNode(int val)
{
	struct Node* newnode = (struct Node*)malloc(sizeof(struct Node));
	if (newnode == NULL)
	{
		perror("BuyRandomNode.malloc");
		return NULL;
	}

	newnode->val = val;
	newnode->next = NULL;
	newnode->random = NULL;
	return newnode;
}
struct Node* copyRandomList(struct Node* head) 
{
	if (head == NULL)
		return NULL;

	// 在原链表的各个节点后链接对应的复制节点
	struct Node* cur = head;
	while (cur != NULL)
	{
		struct Node* copynode = BuyRandomNode(cur->val);
		struct Node* next = cur->next;

		cur->next = copynode;
		copynode->next = next;

		cur = next;
	}

	// 处理复制节点的random
	cur = head;
	while (cur != NULL && cur->next != NULL)
	{
		if (cur->random == NULL)
			cur->next->random = NULL;
		else
			cur->next->random = cur->random->next;

		cur = cur->next->next;
	}

	// 链接各个复制节点为新链表，并且恢复原链表
	struct Node* retList = head->next;
	struct Node* retcur = retList;
	cur = head;
	while (retcur != NULL && retcur->next != NULL)
	{
		struct Node* next = cur->next->next;
		struct Node* retnext = retcur->next->next;
		
		retcur->next = retnext;
		retcur = retnext;

		cur->next = next;
		cur = next;
	}
	cur->next = NULL;

	return retList;
}
int main()
{
	struct Node* List = RandomList();
	struct Node* retlist = copyRandomList(List);
	RandomListPrint(retlist);

	return NULL;
}
*/





/*
struct ListNode* detectCycle(struct ListNode* head) 
{
	if (head == NULL)
		return NULL;

	struct ListNode* fast = head, * slow = head;

	while (fast != NULL && fast->next != NULL)
	{
		slow = slow->next;
		fast = fast->next->next;

		if (fast == slow)
		{
			struct ListNode* meet = slow;
			while (head != meet)
			{
				head = head->next;
				meet = meet->next;
			}
			head->next = NULL;
			return head;
		}
	}

	return NULL;
}
int main()
{
	struct ListNode* list = SList();
	struct ListNode* retnode = detectCycle(list);
	if (retnode)
		ListPrint(retnode);

	return 0;
}
*/






/*
// 给你一个链表的头节点 head ，判断链表中是否有环。
bool hasCycle(struct ListNode* head) 
{
	if (head == NULL)
		return false;

	struct ListNode* fast = head->next, * slow = head;

	while (fast != NULL && fast->next != NULL)
	{
		if (fast == slow)
			return true;

		slow = slow->next;
		fast = fast->next->next;
	}

	return false;
}
int main()
{
	struct ListNode* list = SList();

	if (hasCycle(list))
		printf("is hasCycle\n");
	else
		printf("not hasCycle\n");

	return 0;
}
*/





/*
// 给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点，返回 null 。
int my_abs(int a, int b)
{
	return (((a) > (b)) ? ((a)-(b)) : ((b)-(a)));
}
struct ListNode* getIntersectionNode(struct ListNode* headA, struct ListNode* headB) 
{
	if (headA == NULL)
		return NULL;
	if (headB == NULL)
		return NULL;

	int lenA = 1;
	struct ListNode* curA = headA;
	while (curA->next != NULL)
	{
		lenA++;
		curA = curA->next;
	}

	int lenB = 1;
	struct ListNode* curB = headB;
	while (curB->next != NULL)
	{
		lenB++;
		curB = curB->next;
	}

	if (curA != curB)
		return NULL;


	int gap = my_abs(lenA, lenB);
	struct ListNode* longList = headA;
	struct ListNode* shortList = headB;
	if (lenA < lenB)
	{
		longList = headB;
		shortList = headA;
	}
	while (gap--)
		longList = longList->next;

	while (longList != shortList)
	{
		longList = longList->next;
		shortList = shortList->next;
	}
	
	return longList;
}
int main()
{
	struct ListNode* headA = SList();
	struct ListNode* headB = SList();
	struct ListNode* headC = SList();

	struct ListNode* curA = headA;
	while (curA->next != NULL)
		curA = curA->next;

	struct ListNode* curB = headB;
	while (curB->next != NULL)
		curB = curB->next;

	curA->next = headC;
	curB->next = headC;

	struct ListNode* retList = getIntersectionNode(headA->next, headB);
	ListPrint(retList);

	return 0;
}
*/






/*
// 对于一个链表，请设计一个时间复杂度为O(n),额外空间复杂度为O(1)的算法，判断其是否为回文结构。
// 给定一个链表的头指针A，请返回一个bool值，代表其是否为回文结构。保证链表长度小于等于900。
ListNode* middleNode(ListNode* pHead)
{
	if (pHead == NULL)
		return NULL;

	ListNode* slow = pHead, * fast = pHead;

	while (fast != NULL && fast->next != NULL)
	{
		slow = slow->next;
		fast = fast->next->next;
	}

	return slow;
}
ListNode* reverseList(ListNode* pHead)
{
	if (pHead == NULL)
		return NULL;

	ListNode* tail = pHead;
	while (tail->next != NULL)
		tail = tail->next;

	ListNode* cur = pHead;
	while (cur != tail)
	{
		ListNode* curNext = cur->next;
		cur->next = tail->next;
		tail->next = cur;
		cur = curNext;
	}

	return tail;
}
bool chkPalindrome(ListNode* pHead) 
{
	ListNode* mid = middleNode(pHead);  //找到中间节点
	ListNode* rmid = reverseList(mid);  //从中间节点开始逆置（头插）

	while (rmid != NULL)
	{
		if (rmid->val != pHead->val)
			return false;
		
		rmid = rmid->next;
		pHead = pHead->next;
	}

	return true;
}
int main()
{
	struct ListNode* list = SList();
	if (chkPalindrome(list))
		ListPrint(list);
	else
		printf("not chkPalindrome\n");

	return 0;
}
*/




/*
// 现有一链表的头指针 struct ListNode* pHead ，给一定值x ，编写一段代码将所有小于x的节点排在其余节点之前，
// 且不能改变原来的数据顺序，返回重新排列后的链表的头指针
struct ListNode* partition(struct ListNode* pHead, int x)
{
	if (pHead == NULL)
		return NULL;

	struct ListNode* mineHead = (struct ListNode*)malloc(sizeof(struct ListNode));
	if (mineHead == NULL)
	{
		perror("partition.malloc");
		return NULL;
	}
	struct ListNode* mineTail = mineHead;
	

	struct ListNode* maxHead = (struct ListNode*)malloc(sizeof(struct ListNode));
	if (maxHead == NULL)
	{
		perror("partition.malloc");
		free(mineHead);
		mineHead = mineHead = NULL;
		return NULL;
	}
	struct ListNode* maxTail = maxHead;


	struct ListNode* cur = pHead;
	while (cur != NULL)
	{
		if (cur->val < x)
		{
			mineTail->next = cur;
			mineTail = mineTail->next;
		}
		else
		{
			maxTail->next = cur;
			maxTail = maxTail->next;
		}

		cur = cur->next;
	}

	maxTail->next = NULL;
	mineTail->next = maxHead->next;
	pHead = mineHead->next;

	free(mineHead);
	free(maxHead);

	return pHead;
}
int main()
{
	// 6->5->4->3->2->1->null
	struct ListNode* list = SList();
	struct ListNode* retlist = partition(list, 2);
	// 3->2->1->6->5->4->null
	ListPrint(retlist);

	return 0;
}
*/







/*
//	输入一个链表，输出该链表中倒数第k个结点。
struct ListNode* FindKthToTail(struct ListNode* pListHead, int k) 
{
	if (pListHead == NULL)
		return NULL;

	struct ListNode* fast = pListHead, * slow = pListHead;

	while (k--)
	{
		if (fast == NULL)
			return NULL;

		fast = fast->next;
	}

	while (fast != NULL)
	{
		slow = slow->next;
		fast = fast->next;
	}

	return slow;
}
int main()
{
	// 1->2->3->4->5->6->null
	struct ListNode* list = SList();
	struct ListNode* retlist = FindKthToTail(list, 6);
	ListPrint(retlist);

	return 0;
}
*/





/*
// 给你单链表的头节点 head ，请你反转链表，并返回反转后的链表
struct ListNode* reverseList(struct ListNode* head) 
{
	if (head == NULL)
		return NULL;

	// 找尾节点
	struct ListNode* tail = head;
	while (tail->next != NULL)
		tail = tail->next;

	// 头插
	struct ListNode* cur = head;
	struct ListNode* curnext = NULL;
	while (cur != tail)
	{
		curnext = cur->next;
		cur->next = tail->next;
		tail->next = cur;
		cur = curnext;
	}

	return tail;
}
struct ListNode* reverseList(struct ListNode* head)
{
	if (head == NULL)
		return NULL;

	struct ListNode* n1 = NULL;
	struct ListNode* n2 = head;
	struct ListNode* n3 = NULL;

	while (n2 != NULL)
	{
		n3 = n2->next;
		n2->next = n1;

		n1 = n2;
		n2 = n3;
	}

	return n1;
}
int main()
{
	struct ListNode* list = SList();
	struct ListNode* retlist = reverseList(list);
	ListPrint(retlist);

	return 0;
}
*/



/*
//整数的 数组形式  num 是按照从左到右的顺序表示其数字的数组。
//例如，对于 num = 1321 ，数组形式是[1, 3, 2, 1] 。
//给定 num ，整数的 数组形式 ，和整数 k ，返回 整数 num + k 的 数组形式 。
int* addToArrayForm(int* num, int numSize, int k, int* returnSize) 
{
	int count = 0, tmpk = k;
	while (tmpk)
	{
		tmpk = tmpk / 10;
		count++;
	}
	int max = count > numSize ? count : numSize;
	
	int* retArr = (int*)calloc(max + 1, sizeof(int));
	if (retArr == NULL)
	{
		perror("addToArrayForm.malloc");
		return NULL;
	}
	
	int retEnd = max;          //retArr数组最后一个元素的下标
	int numEnd = numSize - 1;  //num数组最后一个元素的下标
	int carry = 0;             //carry用来记录是否产生进位

	while (numEnd >= 0 || k > 0 || carry > 0) 
	{
		// 取num当前位（若已遍历完则为0）
		int numBit = (numEnd >= 0) ? num[numEnd] : 0;
		// 取k当前位（若已遍历完则为0）
		int kBit = (k > 0) ? (k % 10) : 0;

		// 计算当前位总和（包含进位）
		int sum = numBit + kBit + carry;
		// 更新进位和当前位结果
		carry = sum / 10;
		retArr[retEnd] = sum % 10;

		// 移动指针
		if (numEnd >= 0) 
			numEnd--;
		if (k > 0) 
			k = k / 10;
		
		retEnd--;
	}

	if (retEnd == -1)
	{
		*returnSize = max + 1;
		return retArr;
	}
	else
	{
		*returnSize = max;
		return retArr + 1;
	}
}
int main()
{
	int arr[] = { 9, 9, 9, };
	int returnSize = 0;

	int* retArr = addToArrayForm(arr, sizeof(arr) / sizeof(arr[0]), 9999, &returnSize);

	for (int i = 0; i < returnSize; i++)
		printf("%d ", retArr[i]);

	return 0;
}
*/





/*
// 给定一个整数数组 nums，将数组中的元素向右轮转 k 个位置，其中 k 是非负数。
void reverse(int* nums, int start, int end)
{
	while (start < end)
	{
		int tmp = nums[start];
		nums[start] = nums[end];
		nums[end] = tmp;

		start++;
		end--;
	}
}
void rotate(int* nums, int numsSize, int k) 
{
	if (k >= numsSize)
		k = k % numsSize;

	// 整体逆置
	reverse(nums, 0, numsSize - 1);
	// 逆置前k个
	reverse(nums, 0, k-1);
	// 逆置后numsSize-k个
	reverse(nums, k, numsSize - 1);
}
int main()
{
	int arr[] = { 1,2,3,4,5,6,7 };
	//            7,6,5,4,3,2,1
	//            5,6,7,1,2,3,4       
	// 
	
	rotate(arr, sizeof(arr) / sizeof(arr[0]), 3);

	for (int i = 0; i < sizeof(arr) / sizeof(arr[0]); i++)
		printf("%d ", arr[i]);

	return 0;
}
*/





/*
// 将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。 
struct ListNode
{
	int val;
	struct ListNode* next;
};

struct ListNode* SList()
{
	struct ListNode* n1 = (struct ListNode*)malloc(sizeof(struct ListNode)); assert(n1);
	struct ListNode* n2 = (struct ListNode*)malloc(sizeof(struct ListNode)); assert(n2);
	struct ListNode* n3 = (struct ListNode*)malloc(sizeof(struct ListNode)); assert(n3);
	struct ListNode* n4 = (struct ListNode*)malloc(sizeof(struct ListNode)); assert(n4);
	struct ListNode* n5 = (struct ListNode*)malloc(sizeof(struct ListNode)); assert(n5);
	struct ListNode* n6 = (struct ListNode*)malloc(sizeof(struct ListNode)); assert(n6);

	n1->val = 1;
	n2->val = 2;
	n3->val = 3;
	n4->val = 4;
	n5->val = 5;
	n6->val = 6;

	n1->next = n2;
	n2->next = n3;
	n3->next = n4;
	n4->next = n5;
	n5->next = n6;
	n6->next = NULL;

	return n1;
}
void ListPrint(struct ListNode* list)
{
	assert(list);
	while(list != NULL)
	{
		printf("%d->", list->val);
		list = list->next;
	}
	printf("NULL\n");
}
struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2) 
{
	if (list1 == NULL)
		return list2;
	if (list2 == NULL)
		return list1;

	struct ListNode* retList = NULL, * cur = NULL;

	while (list1 != NULL && list2 != NULL)
	{
		if (list1->val < list2->val)
		{
			if (retList == NULL)
			{
				retList = cur = list1;
			}
			else
			{
				cur->next = list1;
				cur = cur->next;
			}
			
			list1 = list1->next;
		}
		else
		{
			if (retList == NULL)
			{
				retList = cur = list2;
			}
			else
			{
				cur->next = list2;
				cur = cur->next;
			}

			list2 = list2->next;
		}
	}

	if (list1 != NULL)
		cur->next = list1;
	if (list2 != NULL)
		cur->next = list2;
	
	return retList;

}
int main()
{
	struct ListNode* plist1 = SList();
	struct ListNode* plist2 = SList();

	struct ListNode* ret = mergeTwoLists(plist1, plist2);
	ListPrint(ret);

	return 0;
}
*/





/*
// 给你单链表的头结点 head ，请你找出并返回链表的中间结点。
// 如果有两个中间结点，则返回第二个中间结点。
struct ListNode
{
	int val;
	struct ListNode* next;
};

struct ListNode* SList()
{
	struct ListNode* n1 = (struct ListNode*)malloc(sizeof(struct ListNode)); assert(n1);
	struct ListNode* n2 = (struct ListNode*)malloc(sizeof(struct ListNode)); assert(n2);
	struct ListNode* n3 = (struct ListNode*)malloc(sizeof(struct ListNode)); assert(n3);
	struct ListNode* n4 = (struct ListNode*)malloc(sizeof(struct ListNode)); assert(n4);
	struct ListNode* n5 = (struct ListNode*)malloc(sizeof(struct ListNode)); assert(n5);
	struct ListNode* n6 = (struct ListNode*)malloc(sizeof(struct ListNode)); assert(n6);

	n1->val = 1;
	n2->val = 2;
	n3->val = 3;
	n4->val = 4;
	n5->val = 5;
	n6->val = 6;

	n1->next = n2;
	n2->next = n3;
	n3->next = n4;
	n4->next = n5;
	n5->next = n6;
	n6->next = NULL;

	return n1;
}

// 1->null
// 1->2->null
// 1->2->3->4->5->null
// 1->2->3->4->5->6->null
struct ListNode* middleNode(struct ListNode* head) 
{
	if (head == NULL)
		return NULL;

	struct ListNode* slow = head;
	struct ListNode* fast = head->next;

	while (slow != NULL && fast != NULL && fast->next != NULL)
	{
		slow = slow->next;
		fast = fast->next->next;
	}

	if(fast == NULL)
		return slow;
	else
		return slow->next;
}

int main()
{
	struct ListNode* plist = SList();

	struct ListNode* ret = middleNode(plist);
	printf("%d\n", ret->val);

	return 0;
}
*/





/*
// 给你两个按 非递减顺序 排列的整数数组 nums1 和 nums2，另有两个整数 m 和 n ，分别表示 nums1 和 nums2 中的元素数目。
// 请你 合并 nums2 到 nums1 中，使合并后的数组同样按 非递减顺序 排列。
void merge(int* nums1, int nums1Size, int m, int* nums2, int nums2Size, int n) 
{
	int s1 = m - 1;
	int s2 = n - 1;
	int left = nums1Size - 1;

	while (s1 >= 0 && s2 >= 0)
	{
		if (nums1[s1] > nums2[s2])
		{
			nums1[left--] = nums1[s1--];
		}
		else
		{
			nums1[left--] = nums2[s2--];
		}
	}

	while (s2 >= 0)
		nums1[left--] = nums2[s2--];
}
int main()
{
	int arr1[] = { 1,2,7,0,0,0 };
	int arr2[] = { -1,2,6 };

	merge(arr1, sizeof(arr1) / sizeof(arr1[0]), 3, arr2, sizeof(arr2) / sizeof(arr2[0]), 3);

	for (int i = 0; i < 6; i++)
		printf("%d ", arr1[i]);

	return 0;
}
*/





/*
// 给你一个 非严格递增排列 的数组 nums ，请你 原地 删除重复出现的元素，
// 使每个元素 只出现一次 ，返回删除后数组的新长度。元素的 相对顺序 应该保持 一致 。然后返回 nums 中唯一元素的个数。
int removeDuplicates(int* nums, int numsSize) 
{
	int same = 0;

	for (int different = 1; different < numsSize; different++)
	{
		if (nums[same] != nums[different])
		{
			nums[++same] = nums[different];
		}
	}

	return same + 1;
}
int main()
{
	int arr[] = { 0,0,1,1,1,2,2,3,3,4 };
	int ret = removeDuplicates(arr, sizeof(arr) / sizeof(arr[0]));

	for (int i = 0; i < ret; i++)
	{
		printf("%d ", arr[i]);
	}

	return 0;
}
*/



/*
// 给你一个数组 nums 和一个值 val，你需要 原地 移除所有数值等于 val 的元素。
// 元素的顺序可能发生改变。然后返回 nums 中与 val 不同的元素的数量。
int removeElement(int* nums, int numsSize, int val) 
{
	int findval = 0;
	int notval = 0;

	while (findval < numsSize && notval < numsSize)
	{
		if (nums[findval] == val)
		{
			if (nums[notval] != val)
			{
				int tmp = nums[findval];
				nums[findval] = nums[notval];
				nums[notval] = tmp;
			}
			else
			{
				notval++;
			}
		}
		else
		{
			findval++;
			notval++;
		}
	}

	return findval;
}

int main()
{
	int arr[] = { 0,1,2,2,3,0,4,2 };

	removeElement(arr, sizeof(arr) / sizeof(arr[0]), 2);

	return 0;
}
*/



/*
// 整数数组 sockets 记录了一个袜子礼盒的颜色分布情况，
// 其中 sockets[i] 表示该袜子的颜色编号。礼盒中除了一款撞色搭配的袜子，每种颜色的袜子均有两只。
// 请设计一个程序，在时间复杂度 O(n)，空间复杂度O(1) 内找到这双撞色搭配袜子的两个颜色编号。

int* sockCollocation(int* sockets, int socketsSize, int* returnSize)
{
	*returnSize = 2;
	int* returnArr = (int*)calloc(sizeof(int), *returnSize);
	
	int xor = 0;
	for (int i = 0; i < socketsSize; i++)
		xor = xor ^ sockets[i];           

	int m = 1;
	while ((xor &m) == 0)
		m = m << 1;

	for (int i = 0; i < socketsSize; i++)
	{
		if ((sockets[i] & m) == 0)
			returnArr[0] = returnArr[0] ^ sockets[i];
		else
			returnArr[1] = returnArr[1] ^ sockets[i];
	}

	return returnArr;
}

int main()
{
	int sockets[] = { 1,2,3,4,5,1,2,3,4,6 };
	int returnSize[2] = { 0 };
    sockCollocation(sockets, sizeof(sockets) / sizeof(sockets[0]), returnSize);

	printf("%d %d", returnSize[0], returnSize[1]);

	return 0;
}
*/





/*
// 数组nums包含从0到n的所有整数，但其中缺了一个。请编写代码找出那个缺失的整数。你有办法在O(n)时间内完成吗？

// 0-3 = 0+1+2+3 = 6 = (0+3)*4/2 = 6
// 0-5 = 0+1+2+3+4+5 = 15 = (0+5)*6/2 = 15

int missingNumber(int* nums, int numsSize)
{
	int sum = (0 + numsSize) * (numsSize + 1) / 2;

	for (int i = 0; i < numsSize; i++)
	{
		sum = sum - nums[i];
	}

	return sum;
}

int main()
{
	int arr[] = { 9, 6, 4, 2, 3, 5, 7, 0, 1 };

	int ret = missingNumber(arr, sizeof(arr) / sizeof(arr[0]));

	printf("%d\n", ret);

	return 0;
}
*/
